#include<iostream>
#include<vector>
#include<stack>
using namespace std;

  struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode() : val(0), left(nullptr), right(nullptr) {}
      TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
      TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  };
  /*
  class Solution {
     vector<int> Order(TreeNode*root,vector<vector<int>>& ret)
      {
          if (root == nullptr)
          {
              return;
          }

          vector<int> temp1= Order(root->left,ret);
          vector<int> temp2= Order(root->left,ret);



      }
  public:
      vector<vector<int>> levelOrderBottom(TreeNode* root) {
          vector<vector<int>> ret;




      }
  };*/
 
  
 /* struct TreeNode {
      int val;
      struct TreeNode *left;
      struct TreeNode *right;
      TreeNode(int x) :
              val(x), left(NULL), right(NULL) {
                  
      }
  };   
  class Solution {
      void change(TreeNode* root, TreeNode*& preve)
      {
          if (root == nullptr)
          {
              return;
          }
          change(root->left, preve);
          root->left = preve;
          if (preve != nullptr)
          preve->right = root;
          preve = root;
          change(root->right, preve);
      }
  public:
      TreeNode* Convert(TreeNode* pRootOfTree) {
          TreeNode* temp = nullptr;
          change(pRootOfTree, temp);
          if (pRootOfTree == nullptr)
          {
              return nullptr;
          }
          while (true)
          {
              if (pRootOfTree->left == nullptr)
              {
                  return pRootOfTree;
              }
              else
              {
                  pRootOfTree = pRootOfTree->left;
              }
          }

      }
  };*/

  class Solution {
     TreeNode* build(vector<int>& postorder, vector<int>& inorder, int& prei, int begin, int end)
      {
         int rooti = begin;
         if (prei<0||begin>end)
         {
             
             return nullptr;
         }
         TreeNode* root = new TreeNode(postorder[prei]);
         if (begin == end)
         {
             prei--;
             return root;
         }
         while (rooti != end+1)
         {
             if (postorder[prei] == inorder[rooti])
             {
                 prei--;
                 break;
             }
             ++rooti;

         }
         root->right = build(postorder, inorder, prei, rooti + 1, end);
         root->left = build(postorder, inorder, prei, begin, rooti - 1);
         return root;
      }
  public:
      TreeNode* buildTree(vector<int>& postorder, vector<int>& inorder) {
          int prei = postorder.size()-1;
          return  build(postorder, inorder, prei, 0, inorder.size()-1);
          
      };

      void preorder(TreeNode* root,vector<int>& ret)
      {
          if (root == NULL)
          {
              return;
          }
          ret.push_back(root->val);
          preorder(root->left, ret);
          preorder(root->right, ret);
      }

      
      vector<int> preorderTraversal(TreeNode* root) {
         /* vector<int> ret;
          preorder(root, ret);
          return ret;*/
          stack<TreeNode*> temp;
          TreeNode* current = root;
          vector<int> ret;
          while(!(current==nullptr&&temp.empty()))
          {
              while (current!=nullptr)
              {
                  temp.push(current);
                  ret.push_back(current->val);
                  if (current->left != nullptr)
                  {               
                      current = current->left;
                  }
                  else
                  {
                      break;
                  }

              }
              temp.pop();
              if(current!=nullptr)
              current = current->right;
              while(current == nullptr && temp.empty() != true)
              {
                  current = temp.top()->right;
                  temp.pop();
              }

          }

          return ret;
          
         


      }

      vector<int> inorderTraversal(TreeNode* root) {
          stack<TreeNode*> temp;
          TreeNode* current = root;
          vector<int> ret;
          while (!(current == nullptr && temp.empty()))
          {
              while (current != nullptr)
              {
                  temp.push(current);
                  if (current != nullptr)
                  {
                      current = current->left;
                  }
                  else
                  {
                      break;
                  }

              }
              TreeNode* top = temp.top();
              ret.push_back(top->val);
              current = top->right;

              return ret;

             /* ret.push_back(current->val);
              temp.pop();
              while(!(temp.empty()==true&&current==nullptr))
              {
                  if (current->right != nullptr)
                  {
                      current = current->right;
                      break;
                  }
                  else
                  {
                      if (temp.empty() != true)
                      {
                          current = temp.top();
                          ret.push_back(current->val);
                          temp.pop();
                      }
                      else
                      {
                          return ret;
                      }
                  }
              }
          }*/

      }
      vector<int> postorderTraversal(TreeNode* root) {
          stack<TreeNode*> temp;
          TreeNode* current = root;
          TreeNode* preve = root;
          vector<int> ret;
          while (!(current == nullptr && temp.empty()))
          {
              while (current != nullptr)
              {
                  temp.push(current);
                  if (current->left != nullptr)
                  {
                      preve = current;
                      current = current->left;
                  }
                  else
                  {
                      break;
                  }

              }
              while (!(temp.empty() == true && current == nullptr))
              {
                  if (current->right != nullptr&&preve!=current->right)
                  {
                      preve = current;
                      current = current->right;
                      break;
                  }
                  else
                  {
                     
                    ret.push_back(current->val);
                    temp.pop();
                    preve = current;
                    if (temp.empty() != true)
                        current = temp.top();
                    else
                        return ret;
            }
              }
          }

          return ret;

      }
  };

int main()
{
    TreeNode* x = new TreeNode(1);
    /*x->left = new TreeNode(1);
    x->left->left = new TreeNode(0);
    x->left->right = new TreeNode(2);
    x->right = new TreeNode(6);
    x->right->left = new TreeNode(5);
    x->right->right = new TreeNode(7);*/
    x->left = new TreeNode(4);
    x->left->left = new TreeNode(2);
    x->right = new TreeNode(3);
    Solution k;
    //k.Convert(x);
    int arr1[] = { 3,1,2 };
    int arr2[] = { 1,2,3};
    vector<int> preorder(arr1,arr1+sizeof(arr1)/sizeof(int));
    vector<int> inorder(arr2, arr2+sizeof(arr2)/sizeof(int));
    //TreeNode*ret=k.buildTree(preorder, inorder);
    vector<int> yy = k.postorderTraversal(x);
   
    

	return 0;
}